package com.demo.javaDemo.sort;

import java.util.Arrays;

public class HeapSort {

	public static int[] sort(int[] datas) {
		normHeap(datas);
		
		for(int i=datas.length-1;i>0;i--) {
			swag(datas,0,i);
			System.out.println(i+">>>"+Arrays.toString(datas));
			int swagIndex=0;
			while(swagIndex>=0) {
				swagIndex=normHeap(datas,i, swagIndex);
			}
			System.out.println(i+">norm>>"+Arrays.toString(datas));
		}
		return datas;
	}
	
	public static void normHeap(int[] datas) {
		int len=datas.length;
		int high=getTreeHigh(len);
		for(int i=((int)Math.pow(2, high-1))-1;i>=0;i--) {
			// 不需要深层检查
			normHeap(datas,len, i);
		}
	}
	public static int normHeap(int[] datas,int aLen,int topIndex) {
		int leftIndex=topIndex*2+1;
		int rightIndex=topIndex*2+2;
		return normHeap(datas,aLen, topIndex, leftIndex, rightIndex);
	}
	public static int normHeap(int[] datas,int aLen,int topIndex,int leftIndex,int rightIndex) {
		if(leftIndex>=aLen) {
			return -1;
		}
		int maxIndex=leftIndex;
		if(rightIndex<aLen&&datas[rightIndex]>datas[maxIndex]) {
			maxIndex=rightIndex;
		}
		if(datas[maxIndex]>datas[topIndex]) {
			swag(datas,maxIndex,topIndex);
			return maxIndex;
		}
		return -1;
	}
	
	
	public static void swag(int[] datas,int index1,int index2) {
		int station=datas[index1];
		datas[index1]=datas[index2];
		datas[index2]=station;
	}
	
	public static int getTreeHigh(int size) {
		Double h=Math.ceil(Math.log(size)/Math.log(2));
		return h.intValue();
	}
	
	
	public static void main(String[] args) {
		int[] datas= {8,34,3,32,123,235,3,232,64,12};
		System.out.println("begin:"+Arrays.toString(datas));
		sort(datas);
		System.out.println("end:"+Arrays.toString(datas));
	}
	
}
